﻿using System;
using System.Collections.Generic;

namespace ReverseLinkedListII
{
    public class ListNode
    {
        /// <summary>
        /// 值
        /// </summary>
        public int val;

        /// <summary>
        /// 下一个节点
        /// </summary>
        public ListNode next;

        /// <summary>
        /// 构造函数
        /// </summary>
        /// <param name="x">初始化值</param>
        public ListNode(int x) { val = x; }
    }

    public class Solution
    {
        /// <summary>
        /// Reverse a linked list from position m to n.
        /// </summary>
        /// <param name="head">head point</param>
        /// <param name="m">fist position</param>
        /// <param name="n">last position</param>
        /// <returns>the reverse list</returns>
        public ListNode ReverseBetween(ListNode head, int m, int n)
        {
            if (head == null)
            {
                return null;
            }

            // Convert LinkedList to List.
            List<int> list = new List<int>();
            while (head != null)
            {
                list.Add(head.val);
                head = head.next;
            }

            // Reverse the List
            for (int i = m, j = n; i < j; i++, j--)
            {
                int temp = list[i - 1];
                list[i - 1] = list[j - 1];
                list[j - 1] = temp;
            }

            // Convert List to LinkedList
            head = new ListNode(0);
            ListNode p = head;

            for (var i = 0; i < list.Count; i++)
            {
                p.val = list[i];

                if (i + 1 != list.Count)
                {
                    p.next = new ListNode(0);
                    p = p.next;
                }
            }
            
            return head;
        }

        public void PrintListNode(ListNode ln)
        {
            Console.Write("(");
            while (ln != null)
            {
                Console.Write(ln.val);

                if (ln.next != null) Console.Write("->");

                ln = ln.next;
            }

            Console.Write(")");
        }
    }
}